package leetcode;

/**
 * @author yinlei
 * @date 2018/6/19
 * @since 1.0.0
 */
public class N004MedianofTwoSortedArrays {

    public static void main(String[] args) {
        int[] nums1 = {2, 2, 4, 4, 5, 6};
        int[] nums2 = {2, 2, 2, 2, 2};
        double medianSortedArrays = findMedianSortedArrays(nums1, nums2);
        System.out.println(medianSortedArrays);
    }

    static public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int l1 = nums1.length;
        int l2 = nums2.length;
        int total = l1 + l2;

        int[] na = new int[l1 + l2];
        int i1 = 0, i2 = 0, x = 0;

        // 将两个数组合并，原理类似于快速排序方式
        for (; i1 < l1 && i2 < l2 && x < total; x++) {
            int d1 = nums1[i1];
            int d2 = nums2[i2];
            if (d1 > d2) {
                na[x] = d2;
                i2++;
            } else {
                na[x] = d1;
                i1++;
            }
        }

        if (x < total) {
            if (i1 == l1) {
                for (int i = i2; i < l2; i++) {
                    na[x++] = nums2[i];
                }
            }
            if (i2 == l2) {
                for (int i = i1; i < l1; i++) {
                    na[x++] = nums1[i];
                }
            }
        }

        int mid = total / 2;
        double result = na[mid];

        if (total % 2 == 0) {
            result = (na[mid] + na[mid - 1]) / 2.0;
        }

        return result;
    }
}
